package com.jack.leetcode.eachproblem_2020;

/**
 * Created by zhang_j on 2020/11/12
 */
public class 按奇偶数排序数组2 {

    public static void main(String[] args) {
        int[] a = {4,2,5,7};
        sort(a);
    }

    public static int[] sort(int[] A){
        int n = A.length;
        int j = 1;
        for(int i = 0;i < n;i+=2){
            if(A[i] % 2 != 0){
                while(A[j] % 2 != 0){
                    j += 2;
                }

                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }
        }
        return A;
    }

    public static int[] sortArrayByParityII(int[] A) {
        int n = A.length;
        boolean ou = true;
        for(int i = 0;i < n;i++){
            if(ou){
                if(A[i] % 2 != 0){
                    int next = getNext(A, i, ou);
                    if(next != -1){
                        swap(A, i, next);
                    }
                }
                ou = false;
            }else{
                if(A[i] % 2 == 0){
                    int next = getNext(A, i, ou);
                    if(next != -1){
                        swap(A, i, next);
                    }
                }
                ou = true;
            }
        }
        return A;
    }

    private static void swap(int[] A, int i, int j){
        int tmp = A[j];
        A[j] = A[i];
        A[i] = tmp;
    }

    private static int getNext(int[] A, int index, boolean ou){
        if(ou){
            for(int i = index + 1;i < A.length;i++){
                if(i % 2 == 1 && A[i] % 2 == 0){
                    return i;
                }
            }
        }else{
            for(int i = index + 1;i < A.length;i++){
                if(i % 2 == 0 && A[i] % 2 == 1){
                    return i;
                }
            }
        }
        return -1;
    }
}
